

#ifndef BINARYSEARCHTREE_HPP
#define BINARYSEARCHTREE_HPP

//#include "t.hpp"

#define false 0
#define	true 1

#define BinarySearchTree_DEFINE(st_type)\
\
typedef struct node_##st_type{\
	st_type data;\
	struct node_##st_type *left;\
	struct node_##st_type *right;\
	short isleft;\
	short isright;\
}Node_##st_type;\
\
typedef struct BST_##st_type##_Iterator{\
\
	Node_##st_type *cur_node;\
	st_type (*deref)(struct BST_##st_type##_Iterator *);\
	void (*inc)(struct BST_##st_type##_Iterator *);\
	void (*dec)(struct BST_##st_type##_Iterator *);\
\
}BinarySearchTree_##st_type##_Iterator;\
\
\
typedef struct BinarySearchTree_##st_type {\
\
	char type[100];\
	Node_##st_type *root;\
	BinarySearchTree_##st_type##_Iterator (*insert)(struct BinarySearchTree_##st_type *bst, st_type pr);\
	BinarySearchTree_##st_type##_Iterator& (*begin)(struct BinarySearchTree_##st_type *bst);\
	BinarySearchTree_##st_type##_Iterator& (*end)(struct BinarySearchTree_##st_type *bst);\
	void (*erase) (BinarySearchTree_##st_type *bst, BinarySearchTree_##st_type##_Iterator it);\
	void (*delet) (BinarySearchTree_##st_type *bst);\
	bool(*compare)(const st_type &p1, const st_type &p2);\
}BinarySearchTree_##st_type;\
\
st_type it_deref (BinarySearchTree_##st_type##_Iterator *it){\
\
	return (st_type)(it->cur_node->data);\
}\
\
/* Threaded insert */\
int insert_element (Node_##st_type *root, st_type pr, BinarySearchTree_##st_type##_Iterator *it, BinarySearchTree_##st_type *bst){\
	Node_##st_type *tmp, *new_node;\
\
	new_node = (Node_##st_type *) malloc (sizeof(Node_##st_type)); /* TODO: Free this after use */\
	if (!new_node){\
		printf ("Not enough memory \n");\
		exit(1);\
	}\
	new_node->data = pr;\
	new_node->left = NULL;\
	new_node->right = NULL;\
	new_node->isleft = true;\
	new_node->isright = true;\
\
	if (!root){\
		root = new_node;\
		return 0;\
\
	}else{\
		tmp = root;\
		while (1){\
			 /*if (strcmp(tmp->data->name, pr->name) > 0){*/\
			 if (bst->compare(tmp->data, pr) == 0){\
			 	if (tmp->isleft == false){\
					tmp = tmp->left;\
				}\
				else{\
					new_node->left = tmp->left;\
					tmp->left = new_node;\
					new_node->right = tmp;\
					tmp->isleft = false;\
					new_node->isright = true;\
					it->cur_node = new_node; /* Return a pointer to in Iterator */\
					return 0;\
				}\
			 }\
			 else if(bst->compare(tmp->data, pr)!= 0) {\
			 	if (tmp->isright == false){\
					tmp = tmp->right;\
				}\
				else{\
					new_node->right = tmp->right;\
					tmp->right = new_node;\
					new_node->left = tmp;\
					tmp->isright = false;\
					new_node->isleft = true;\
					it->cur_node = new_node; /* Return a pointer to in Iterator */\
					return 0;\
				}\
			 }\
			 else\
			 	return 1;\
		}\
	}\
}\
\
void it_inc (BinarySearchTree_##st_type##_Iterator *it){\
	Node_##st_type *t_node = it->cur_node;\
	/*old:*/\
	/*it->cur_node = t_node->right;*/\
	\
	/* new:*/\
	if (t_node){\
		if (t_node->isright == false){\
			t_node = t_node->right;\
			if (t_node->isleft == false)\
				t_node = t_node->left;\
			it->cur_node = t_node;\
			return;\
		}\
		else{\
			it->cur_node = t_node->right;\
			return;\
		}\
	}\
\
}\
\
void it_dec (BinarySearchTree_##st_type##_Iterator *it){\
	Node_##st_type *t_node = it->cur_node;\
\
	if (t_node->left == NULL)\
		return; /* Reached at right end */\
\
	it->cur_node = t_node->left;\
}\
\
BinarySearchTree_##st_type##_Iterator insert_node (BinarySearchTree_##st_type *bst, st_type pr){\
\
	BinarySearchTree_##st_type##_Iterator it;\
	it.cur_node = NULL;\
	it.deref = it_deref;\
	it.inc = it_inc;\
	it.dec = it_dec;\
\
	if (!bst->root){\
		bst->root = (Node_##st_type *) malloc (sizeof(Node_##st_type)); /* TODO: Free this after use */\
		if (!bst->root){\
			printf ("Not enough memory \n");\
			exit(1);\
		}\
		bst->root->data = pr;\
		bst->root->left = NULL;\
		bst->root->right = NULL;\
		bst->root->isleft = true;\
		bst->root->isright = true;\
\
		it.cur_node = bst->root;\
	}\
	else{\
		if ((insert_element(bst->root, pr, &it, bst))){\
			/* Set the Iterator to it_end() if the pr element is already in the BST */\
			/*printf ("Setting iterator to end() because '%s' is already in the BST\n",pr->name);*/\
			it.cur_node = (Node_##st_type *) malloc (sizeof (Node_##st_type)); /* TODO: Free this after use i.e. free the calling iterator. Check if it is OK to set cur_node NULL for it_end(); */\
			if (!it.cur_node){\
				printf ("Not enough memory \n");\
				exit (1);\
			}\
			it.cur_node->left = NULL;\
			it.cur_node->right = NULL;\
		}\
	}\
	return it;\
}\
\
Node_##st_type * get_parent(Node_##st_type *root, Node_##st_type *cur, BinarySearchTree_##st_type *bst){\
\
	Node_##st_type *tmp;\
	if (root->left == cur || root->right == cur )\
		return root;\
	else{\
		if (bst->compare(root->data, cur->data) == 0)\
			tmp =  get_parent (root->left, cur, bst); /* Add to left */\
		else if (bst->compare(root->data, cur->data) != 0)\
			tmp = get_parent (root->right, cur, bst); /* Add to right */\
\
		return tmp;\
	}\
}\
\
Node_##st_type * get_successor(Node_##st_type *root){\
\
	Node_##st_type *tmp = root;\
	if (!root) return NULL;\
\
	while (tmp->isleft == false){\
		tmp = tmp->left;\
	}\
	return tmp;\
}\
\
int __erase_node (Node_##st_type *tree, BinarySearchTree_##st_type##_Iterator it, BinarySearchTree_##st_type *bst){\
\
	Node_##st_type *curr = it.cur_node;\
	Node_##st_type *parent = NULL, *succ = NULL, *succ_parent = NULL;\
\
	if(!tree) return 0;\
\
	/* TODO: Case: if node tobe delete is root node */\
\
	if (curr != tree)\
		parent = get_parent(tree, curr, bst);\
\
	while (1){\
		if (curr->isleft && curr->isright){\
			/* 'it' node has no children */\
\
			if (curr == tree){\
				free(curr);\
				return 0;\
			}\
			if (parent->left == curr){\
				parent->isleft = true;\
				parent->left = curr->left;\
			}\
			else{\
				parent->isright = true;\
				parent->right = curr->right;\
			}\
\
			free (it.cur_node);\
			it.cur_node = NULL;\
			return 0;\
		}\
		else if (!curr->isleft  && curr->isright){\
			/* If 'it' node has one left child */\
\
			if (curr == tree){\
				curr = curr->left;\
				tree->data = curr->data;\
				tree->left = curr->left;\
				if (curr->isright == true)\
					tree->right = NULL;\
				else\
					tree->right = curr->right;\
\
				tree->isleft = curr->isleft;\
				tree->isright = curr->isright;\
\
				free(curr);\
				return 0;\
			}\
			if (parent->left == curr){\
				parent->left = curr->left;\
				curr->left->right = parent;\
			}\
			else{\
				parent->right = curr->left;\
				curr->left->right = curr->right;\
			}\
\
			it.cur_node->left = NULL;\
			it.cur_node->right = NULL;\
\
			free(it.cur_node);\
			it.cur_node = NULL;\
			return 0;\
		}\
		else if(curr->isleft && !curr->isright){\
			/* If 'it' node has one right child */\
			\
			if (curr == tree){\
				/*curr = curr->right;\
				tree->data = curr->data;\
				tree->right = curr->right;\
				if (curr->isleft == true)\
				tree->left = NULL;\
				else\
				tree->left = curr->left;\
				\
				tree->isright = curr->isright;\
				tree->isleft = curr->isleft;\
				\
				free(curr);\
				return 0;*/\
				if (curr->right->left == NULL){\
					curr = curr->right;\
					tree->data = curr->data;\
					tree->right = curr->right;\
					tree->left = curr->left;\
					tree->isleft = NULL;\
					tree->isright = curr->isright;\
					free(curr);\
					return 0;\
				}else{\
					curr = curr->right->left;\
					tree->right->left = curr->right;\
					tree->data = curr->data;\
					curr->right->left = curr->left;\
					curr->right->isleft = curr->isleft;\
					free(curr);\
					return 0;\
				}\
\
			}\
			if (parent->left == curr){\
				parent->left = curr->right;\
				curr->right->left = curr->left;\
			}\
			else{\
				parent->right = curr->right;\
				curr->right->left = parent;\
			}\
			\
			it.cur_node->left = NULL;\
			it.cur_node->right = NULL;\
\
			free(it.cur_node);\
			it.cur_node = NULL;\
			return 0;\
\
		}\
		else {\
			/* 'it' has 2 childern */\
			if (curr == tree){\
				parent = NULL;\
				succ = get_successor(curr->right);\
				if (succ == curr->right){\
					succ->left = curr->left;\
					succ->isleft = curr->isleft;\
					free(curr);\
					it.cur_node = NULL;\
					return 0;\
				}\
				else{\
					succ = get_successor(curr->right);\
					succ_parent = get_parent (tree, succ, bst);\
\
					if (succ->isright){\
						succ_parent->isleft = true;\
						succ_parent->left = succ->left;\
					}else{\
\
						succ_parent->left = succ->right;\
						succ->right->left = succ->left;\
					}\
					curr->data = succ->data;\
					free(succ);\
					it.cur_node = NULL;\
					return 0;\
				}\
			}\
			else{\
				succ = get_successor(curr->right);\
				succ_parent = get_parent (tree, succ,bst);\
\
				if (succ->isright){\
					succ_parent->isleft = true;\
					succ_parent->left = succ->left;\
				}else{\
\
					succ_parent->left = succ->right;\
					succ->right->left = succ->left;\
				}\
				curr->data = succ->data;\
				free(succ);\
				it.cur_node = NULL;\
				return 0;\
			}\
		}	\
	}\
\
	return 1;\
}\
\
void erase_node (BinarySearchTree_##st_type *bst, BinarySearchTree_##st_type##_Iterator it){\
\
	/*printf("Erasing '%s'\n", it.cur_node->data->name);*/\
	__erase_node(bst->root, it,bst);\
}\
\
BinarySearchTree_##st_type##_Iterator& it_begin (BinarySearchTree_##st_type *bst){\
	\
	static BinarySearchTree_##st_type##_Iterator b_tmp;\
	Node_##st_type *tmp = bst->root;\
	\
	if (tmp ){\
		while (tmp->left != NULL)\
			tmp = tmp->left;\
	}\
	b_tmp.cur_node = tmp;\
	b_tmp.deref = it_deref;\
	b_tmp.inc = it_inc;\
	b_tmp.dec = it_dec;\
	return (b_tmp);\
}\
\
BinarySearchTree_##st_type##_Iterator& it_end (BinarySearchTree_##st_type *bst){\
	\
	static BinarySearchTree_##st_type##_Iterator e_tmp;\
\
	Node_##st_type *tmp = bst->root;\
\
\
	e_tmp.cur_node = (Node_##st_type *) malloc (sizeof (Node_##st_type)); /* TODO: Free this after use i.e. free the calling iterator; Check if it is OK to set cur_node NULL for it_end(); */\
	if (!e_tmp.cur_node){\
		printf ("Not enough memory \n");\
		exit (1);\
	}\
	\
	if (tmp){\
		while (tmp->right != NULL)\
			tmp = tmp->right;\
	}\
\
	/* TODO: Confirm this if to assing NULL to every field */\
	e_tmp.cur_node->left = tmp;\
	/*e_tmp.cur_node->data = (st_type)0;*/\
	e_tmp.deref = it_deref;\
	e_tmp.inc = it_inc;\
	e_tmp.dec = it_dec;\
	\
	return (e_tmp);\
}\
\
/* TODO: Confirm what to return when i.e. returning 1 if the elements are same or not */\
int BinarySearchTree_##st_type##_Iterator_equal (BinarySearchTree_##st_type##_Iterator it, BinarySearchTree_##st_type##_Iterator it_end){\
\
	if (it_end.cur_node == NULL)\
		return 1;\
	if (it.cur_node == NULL)\
		return 1;\
	if (it.cur_node == it_end.cur_node)\
		return 1;\
	else\
		return 0;\
}\
\
/* TODO: Check the struct of tree once again. While deleting the tree it is giving double free corruption */\
Node_##st_type * free_tree(Node_##st_type *root){\
	\
	if (root != NULL){\
		if (root->isleft == false)\
			root->left = free_tree (root->left);\
		if (root->isright == false)	\
			root->right = free_tree (root->right);\
		/*if (root->data )*/\
			/*root->data = NULL;*/\
		if (root)	\
			free(root);\
		root = NULL;\
		return root;\
	}\
	return root;\
}\
\
void bst_delet (BinarySearchTree_##st_type *bst){\
\
	printf ("Deleting BST\n");\
	free_tree(bst->root);\
}\
\
BinarySearchTree_##st_type* BinarySearchTree_##st_type##_new (bool(*fptr_less)(const st_type &p1, const st_type &p2)){\
	\
	/* TODO: 1. Later set a comparision function here */\
        /*       2. Set type field */\
	BinarySearchTree_##st_type *new_bst;\
\
	new_bst = (BinarySearchTree_##st_type *) malloc (sizeof (BinarySearchTree_##st_type));  /*  TODO: Free this after use */\
	if (!new_bst){\
		printf ("Not enough memory \n");\
		exit (1);\
	}\
\
	new_bst->root = NULL;\
	new_bst->insert = insert_node;\
	new_bst->erase = erase_node;\
	new_bst->begin = it_begin;\
	new_bst->end = it_end;\
	new_bst->delet = bst_delet;\
	new_bst->compare = fptr_less;\
	return new_bst;\
}
#endif /* #ifndef BINARYSEARCHTREE_HPP */
